Fight in Ninja World

3.7

32 votes
BFS, Disjoint Set, DFS, Easy
Problem

In Ninja World, World War is going on..

The Raikage Army and Zetsu Army are fighting each other. The war has become so fierce that, no one knows who will win. The ninjas of Leaf Village want to know who will survive finally. But leaf village ninjas are afraid of going to the battlefield.

So, they made a plan. They collected the information from the newspapers of Cloud Village(where the Raikage Army is from) and Kabutos territory(where the Zetsu Army is from). They found the information about all the dual fights. Dual fight means a fight between a member of Raikage Army and a member of Zetsu Army.

Every solider of Raikage Army as well as of Zetsu Army have been allotted a unique id. The ninjas of Leaf Village knows the id of the dual fighters, but don't know which id belongs to Raikage Army or a Zetsu Army.

Actually, they want to find the maximum possible number of soldiers of Raikage Army. But since they are not good at programming so they ask for your help. You as Naruto of the Hidden Leaf Village solve the problem for the Leaf Village ninjas.

Input Format

Input starts with an integer T , denoting the number of test cases.

Each case contains an integer N denoting the number of dual fights. Each of the next N lines will contain two different integers A,B denoting there was a fight between soldiers having id A and B.

Output Format

For each case, print the case number and the maximum possible members(soldiers) of Raikage Army.

Constraints

1 <= T <= 20
1 <= N <= 105
1 <= A, B <= 2*104

Given that both A & B will be of different army.

NOTE :-- USE FAST I/O METHODS.

Problem Setter : Ayush Verma
Problem Tester : Pranjul Dubey

Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

For Case 1:- Here {2} can belong to zetsu army and {1,3,4,5} can belong to raikage army.... So, the maximum number of soliders that can belong to raikage army is 4

For Case 2:- Here {2,5,4,7} can belong to zetsu army and {6,1,3,9,8,10} can belong to raikage army.... So, the maximum number of soliders that can belong to raikage army is 6

For Case 4:- Here {2,4} can belong to zetsu army and {1,3,5} can belong to raikage army....

Editor Image

?